1. Field of the Invention
The present invention relates generally to linear feedback shift registers (LFSRs), and more particularly to an efficient implementation of an LFSR using split-table lookup.
2. Description of the Related Art
A shift register is a device used in digital logic systems to store and shift multi-bit units of information in synchronization with the pulses of a clock signal. It is an m-cell device whose cells are linked serially, output-to-input. An m-bit digital word may be shifted left or right by one bit position with each clock pulse. Following each shift, an end bit (the "output" bit) of the word is lost, having been shifted out of the register's last cell, while a new bit (the "input" bit) has been added to the appropriate end of the word through the first cell of the register. Following each shift, the entire word in the register may be obtained by parallel access to the outputs of the cells.
Linear feedback shift registers (LFSRs) are shift registers through which binary data moves serially. As is the case with shift registers in general, during each cycle of data transfer, an input bit is fed into the first cell of the LFSR, and each bit in the LFSR shifts down one cell. The bit in the last cell is shifted out of the LFSR as an output bit. In practice, when referring to the number of cells in an LFSR, the term "number of bits" is often used to convey the same meaning.
In contrast to other types of shift registers, however, the input to an LFSR generally is a combination of its output bit and one or more of the bits in predetermined cells (referred to as "taps") of the register, with the combination being fed back as the next input bit. For example, the bits to be combined may be compared using what is referred to as an "exclusive OR" operation, in which a binary zero results from the combination when the bits are of equal value, and a binary one results when the bits are unequal. It happens that with this structure, LFSRs are useful for many applications, such as cyclic redundancy check (CRC) circuits that are used to detect errors in digital transmissions, and pseudorandom number generators used in cryptology, digital video disks, and digital wireless telephones.
In certain of the above-mentioned applications, and particularly for digital video disk (DVD) applications, it is often desirable to undertake the LFSR functions quickly by using a software implementation of the LFSR for enhanced system flexibility and to facilitate the high rates at which data must be transferred in DVDs.